/************************************************************************/
/* Modify from RapidXml v1.13.                                          */
/************************************************************************/

#ifndef __NIGHTXML_H__
#define __NIGHTXML_H__

#include "cstdlib"
#include "new"

#include "NightAssertion.h"


namespace NE
{

	// Size of static memory block of XmlMemoryPool.
	// No dynamic memory allocations are performed by XmlMemoryPool until static memory is exhausted.
	const std::size_t XML_STATIC_POOL_SIZE = 64 * 1024;

	// Size of dynamic memory block of XmlMemoryPool.
	// After the static block is exhausted, dynamic blocks with approximately this size are allocated by XmlMemoryPool.
	const std::size_t XML_DYNAMIC_POOL_SIZE = 64 * 1024;

	// Memory allocation alignment.
	// All memory allocations for nodes, attributes and strings will be aligned to this value.
	// This must be a power of 2 and at least 1, otherwise XmlMemoryPool will not work.
	const std::size_t XML_ALIGNMENT = sizeof(void*);

	// Forward declarations
	template<typename tchar> class XmlNode;
	template<typename tchar> class XmlAttribute;
	template<typename tchar> class XmlDocument;

	//! Enumeration listing all node types produced by the parser.
	//! Use XmlNode::type() function to query node type.
	enum XmlNodeType
	{
		XML_NODE_DOCUMENT,		//!< A document node. Name and value are empty.
		XML_NODE_ELEMENT,		//!< An element node. Name contains element name. Value contains text of first data node.
		XML_NODE_DATA,			//!< A data node. Name is empty. Value contains data text.
		XML_NODE_CDATA,			//!< A CDATA node. Name is empty. Value contains data text.
		XML_NODE_COMMENT,		//!< A comment node. Name is empty. Value contains comment text.
		XML_NODE_DECLARATION,	//!< A declaration node. Name and value are empty. Declaration parameters (version, encoding and standalone) are in node attributes.
		XML_NODE_DOCTYPE,		//!< A DOCTYPE node. Name is empty. Value contains DOCTYPE text.
		XML_NODE_PI				//!< A PI node. Name contains target. Value contains instructions.
	};


	///////////////////////////////////////////////////////////////////////
	// Parsing flags

	//! Parse flag instructing the parser to not create data nodes.
	//! Text of first data node will still be placed in value of parent element, unless xml_parse_no_element_values flag is also specified.
	//! Can be combined with other flags by use of | operator.
	//! <br><br>
	//! See XmlDocument::parse() function.
	const int xml_parse_no_data_nodes = 0x1;

	//! Parse flag instructing the parser to not use text of first data node as a value of parent element.
	//! Can be combined with other flags by use of | operator.
	//! Note that child data nodes of element node take precedence over its value when printing.
	//! That is, if element has one or more child data nodes <em>and</em> a value, the value will be ignored.
	//! Use xml_parse_no_data_nodes flag to prevent creation of data nodes if you want to manipulate data using values of elements.
	//! <br><br>
	//! See XmlDocument::parse() function.
	const int xml_parse_no_element_values = 0x2;

	//! Parse flag instructing the parser to not place zero terminators after strings in the source text.
	//! By default zero terminators are placed, modifying source text.
	//! Can be combined with other flags by use of | operator.
	//! <br><br>
	//! See XmlDocument::parse() function.
	const int xml_parse_no_string_terminators = 0x4;

	//! Parse flag instructing the parser to not translate entities in the source text.
	//! By default entities are translated, modifying source text.
	//! Can be combined with other flags by use of | operator.
	//! <br><br>
	//! See XmlDocument::parse() function.
	const int xml_parse_no_entity_translation = 0x8;

	//! Parse flag instructing the parser to disable UTF-8 handling and assume plain 8 bit characters.
	//! By default, UTF-8 handling is enabled.
	//! Can be combined with other flags by use of | operator.
	//! <br><br>
	//! See XmlDocument::parse() function.
	const int xml_parse_no_utf8 = 0x10;

	//! Parse flag instructing the parser to create XML declaration node.
	//! By default, declaration node is not created.
	//! Can be combined with other flags by use of | operator.
	//! <br><br>
	//! See XmlDocument::parse() function.
	const int xml_parse_declaration_node = 0x20;

	//! Parse flag instructing the parser to create comments nodes.
	//! By default, comment nodes are not created.
	//! Can be combined with other flags by use of | operator.
	//! <br><br>
	//! See XmlDocument::parse() function.
	const int xml_parse_comment_nodes = 0x40;

	//! Parse flag instructing the parser to create DOCTYPE node.
	//! By default, doctype node is not created.
	//! Although W3C specification allows at most one DOCTYPE node, RapidXml will silently accept documents with more than one.
	//! Can be combined with other flags by use of | operator.
	//! <br><br>
	//! See XmlDocument::parse() function.
	const int xml_parse_doctype_node = 0x80;

	//! Parse flag instructing the parser to create PI nodes.
	//! By default, PI nodes are not created.
	//! Can be combined with other flags by use of | operator.
	//! <br><br>
	//! See XmlDocument::parse() function.
	const int xml_parse_pi_nodes = 0x100;

	//! Parse flag instructing the parser to validate closing tag names.
	//! If not set, name inside closing tag is irrelevant to the parser.
	//! By default, closing tags are not validated.
	//! Can be combined with other flags by use of | operator.
	//! <br><br>
	//! See XmlDocument::parse() function.
	const int xml_parse_validate_closing_tags = 0x200;

	//! Parse flag instructing the parser to trim all leading and trailing whitespace of data nodes.
	//! By default, whitespace is not trimmed.
	//! This flag does not cause the parser to modify source text.
	//! Can be combined with other flags by use of | operator.
	//! <br><br>
	//! See XmlDocument::parse() function.
	const int xml_parse_trim_whitespace = 0x400;

	//! Parse flag instructing the parser to condense all whitespace runs of data nodes to a single space character.
	//! Trimming of leading and trailing whitespace of data is controlled by xml_parse_trim_whitespace flag.
	//! By default, whitespace is not normalized.
	//! If this flag is specified, source text will be modified.
	//! Can be combined with other flags by use of | operator.
	//! <br><br>
	//! See XmlDocument::parse() function.
	const int xml_parse_normalize_whitespace = 0x800;

	// Compound flags

	//! Parse flags which represent default behavior of the parser.
	//! This is always equal to 0, so that all other flags can be simply ored together.
	//! Normally there is no need to inconveniently disable flags by anding with their negated (~) values.
	//! This also means that meaning of each flag is a <i>negation</i> of the default setting.
	//! For example, if flag name is xml_parse_no_utf8, it means that utf-8 is <i>enabled</i> by default,
	//! and using the flag will disable it.
	//! <br><br>
	//! See XmlDocument::parse() function.
	const int xml_parse_default = 0;

	//! A combination of parse flags that forbids any modifications of the source text.
	//! This also results in faster parsing. However, note that the following will occur:
	//! <ul>
	//! <li>names and values of nodes will not be zero terminated, you have to use XmlBase::nameSize() and XmlBase::valueSize() functions to determine where name and value ends</li>
	//! <li>entities will not be translated</li>
	//! <li>whitespace will not be normalized</li>
	//! </ul>
	//! See XmlDocument::parse() function.
	const int xml_parse_non_destructive = xml_parse_no_string_terminators | xml_parse_no_entity_translation;

	//! A combination of parse flags resulting in fastest possible parsing, without sacrificing important data.
	//! <br><br>
	//! See XmlDocument::parse() function.
	const int xml_parse_fastest = xml_parse_non_destructive | xml_parse_no_data_nodes;

	//! A combination of parse flags resulting in largest amount of data being extracted.
	//! This usually results in slowest parsing.
	//! <br><br>
	//! See XmlDocument::parse() function.
	const int xml_parse_full = xml_parse_declaration_node | xml_parse_comment_nodes | xml_parse_doctype_node | xml_parse_pi_nodes | xml_parse_validate_closing_tags;


	///////////////////////////////////////////////////////////////////////
	// Memory pool

	//! This class is used by the parser to create new nodes and attributes, without overheads of dynamic memory allocation.
	//! In most cases, you will not need to use this class directly.
	//! However, if you need to create nodes manually or modify names/values of nodes,
	//! you are encouraged to use XmlMemoryPool of relevant XmlDocument to allocate the memory.
	//! Not only is this faster than allocating them by using <code>new</code> operator,
	//! but also their lifetime will be tied to the lifetime of document,
	//! possibly simplifying memory management.
	//! <br><br>
	//! Call allocateNode() or allocateAttribute() functions to obtain new nodes or attributes from the pool.
	//! You can also call allocateString() function to allocate strings.
	//! Such strings can then be used as names or values of nodes without worrying about their lifetime.
	//! Note that there is no <code>free()</code> function -- all allocations are freed at once when clear() function is called,
	//! or when the pool is destroyed.
	//! <br><br>
	//! It is also possible to create a standalone XmlMemoryPool, and use it
	//! to allocate nodes, whose lifetime will not be tied to any document.
	//! <br><br>
	//! Pool maintains <code>XML_STATIC_POOL_SIZE</code> bytes of statically allocated memory.
	//! Until static memory is exhausted, no dynamic memory allocations are done.
	//! When static memory is exhausted, pool allocates additional blocks of memory of size <code>XML_DYNAMIC_POOL_SIZE</code> each,
	//! by using global <code>new[]</code> and <code>delete[]</code> operators.
	//! This behavior can be changed by setting custom allocation routines.
	//! Use setAllocator() function to set them.
	//! <br><br>
	//! Allocations for nodes, attributes and strings are aligned at <code>XML_ALIGNMENT</code> bytes.
	//! This value defaults to the size of pointer on target architecture.
	//! <br><br>
	//! To obtain absolutely top performance from the parser,
	//! it is important that all nodes are allocated from a single, contiguous block of memory.
	//! Otherwise, cache misses when jumping between two (or more) disjoint blocks of memory can slow down parsing quite considerably.
	//! If required, you can tweak <code>XML_STATIC_POOL_SIZE</code>, <code>XML_DYNAMIC_POOL_SIZE</code> and <code>XML_ALIGNMENT</code>
	//! to obtain best wasted memory to performance compromise.
	//! To do it, define their values before NightXML.h file is included.
	//! \param tchar Character type of created nodes.
	template<typename tchar = char>
	class XmlMemoryPool
	{
	public:
		//! \cond Internal
		typedef void *(allocFunc)(std::size_t);		// Type of user-defined function used to allocate memory
		typedef void (freeFunc)(void *);			// Type of user-defined function used to free memory
		//! \endcond

		//! Constructs empty pool with default allocator functions.
		XmlMemoryPool(void);

		//! Destroys pool and frees all the memory.
		//! This causes memory occupied by nodes allocated by the pool to be freed.
		//! Nodes allocated from the pool are no longer valid.
		~XmlMemoryPool(void);

		//! Allocates a new node from the pool, and optionally assigns name and value to it.
		//! If the allocation request cannot be accomodated, this function will throw <code>std::bad_alloc</code>.
		//! If exceptions are disabled by defining XML_NO_EXCEPTIONS, this function
		//! will call xml_parse_error_handler() function.
		//! \param type Type of node to create.
		//! \param name Name to assign to the node, or 0 to assign no name.
		//! \param value Value to assign to the node, or 0 to assign no value.
		//! \param name_size Size of name to assign, or 0 to automatically calculate size from name string.
		//! \param value_size Size of value to assign, or 0 to automatically calculate size from value string.
		//! \return Pointer to allocated node. This pointer will never be NULL.
		XmlNode<tchar> *allocateNode(XmlNodeType type,
			const tchar *name = 0, const tchar *value = 0,
			std::size_t name_size = 0, std::size_t value_size = 0);

		//! Allocates a new attribute from the pool, and optionally assigns name and value to it.
		//! If the allocation request cannot be accomodated, this function will throw <code>std::bad_alloc</code>.
		//! If exceptions are disabled by defining XML_NO_EXCEPTIONS, this function
		//! will call xml_parse_error_handler() function.
		//! \param name Name to assign to the attribute, or 0 to assign no name.
		//! \param value Value to assign to the attribute, or 0 to assign no value.
		//! \param name_size Size of name to assign, or 0 to automatically calculate size from name string.
		//! \param value_size Size of value to assign, or 0 to automatically calculate size from value string.
		//! \return Pointer to allocated attribute. This pointer will never be NULL.
		XmlAttribute<tchar> *allocateAttribute(const tchar *name = 0, const tchar *value = 0,
			std::size_t name_size = 0, std::size_t value_size = 0);

		//! Allocates a char array of given size from the pool, and optionally copies a given string to it.
		//! If the allocation request cannot be accomodated, this function will throw <code>std::bad_alloc</code>.
		//! If exceptions are disabled by defining XML_NO_EXCEPTIONS, this function
		//! will call xml_parse_error_handler() function.
		//! \param source String to initialize the allocated memory with, or 0 to not initialize it.
		//! \param size Number of characters to allocate, or zero to calculate it automatically from source string length; if size is 0, source string must be specified and null terminated.
		//! \return Pointer to allocated char array. This pointer will never be NULL.
		tchar *allocateString(const tchar *source = 0, std::size_t size = 0);

		//! Clones an XmlNode and its hierarchy of child nodes and attributes.
		//! Nodes and attributes are allocated from this memory pool.
		//! Names and values are not cloned, they are shared between the clone and the source.
		//! Result node can be optionally specified as a second parameter,
		//! in which case its contents will be replaced with cloned source node.
		//! This is useful when you want to clone entire document.
		//! \param source Node to clone.
		//! \param result Node to put results in, or 0 to automatically allocate result node
		//! \return Pointer to cloned node. This pointer will never be NULL.
		XmlNode<tchar> *cloneNode(const XmlNode<tchar> *source, XmlNode<tchar> *result = 0);

		//! Clears the pool.
		//! This causes memory occupied by nodes allocated by the pool to be freed.
		//! Any nodes or strings allocated from the pool will no longer be valid.
		void clear();

		//! Sets or resets the user-defined memory allocation functions for the pool.
		//! This can only be called when no memory is allocated from the pool yet, otherwise results are undefined.
		//! Allocation function must not return invalid pointer on failure. It should either throw,
		//! stop the program, or use <code>longjmp()</code> function to pass control to other place of program.
		//! If it returns invalid pointer, results are undefined.
		//! <br><br>
		//! User defined allocation functions must have the following forms:
		//! <br><code>
		//! <br>void *allocate(std::size_t size);
		//! <br>void free(void *pointer);
		//! </code><br>
		//! \param af Allocation function, or 0 to restore default function
		//! \param ff Free function, or 0 to restore default function
		void setAllocator(allocFunc *af, freeFunc *ff);

	private:
		struct header
		{
			char *previous_begin;
		};

		void init();

		char *align(char *ptr);

		char *allocateRaw(std::size_t size);

		void *allocateAligned(std::size_t size);

		char *mBegin;									// Start of raw memory making up current pool
		char *mPtr;										// First free byte in current pool
		char *mEnd;										// One past last available byte in current pool
		char mStaticMemory[XML_STATIC_POOL_SIZE];		// Static raw memory
		allocFunc *mAllocFunc;							// Allocator function, or 0 if default is to be used
		freeFunc *mFreeFunc;							// Free function, or 0 if default is to be used
	};


	///////////////////////////////////////////////////////////////////////////
	// XML base

	//! Base class for XmlNode and XmlAttribute implementing common functions:
	//! name(), nameSize(), value(), valueSize() and parent().
	//! \param tchar Character type to use
	template<typename tchar = char>
	class XmlBase
	{
	public:
		///////////////////////////////////////////////////////////////////////////
		// Construction & destruction

		// Construct a base with empty name, value and parent
		XmlBase(void);

		///////////////////////////////////////////////////////////////////////////
		// Node data access

		//! Gets name of the node.
		//! Interpretation of name depends on type of node.
		//! Note that name will not be zero-terminated if xml_parse_no_string_terminators option was selected during parse.
		//! <br><br>
		//! Use nameSize() function to determine length of the name.
		//! \return Name of node, or empty string if node has no name.
		tchar *getName() const;

		//! Gets size of node name, not including terminator character.
		//! This function works correctly irrespective of whether name is or is not zero terminated.
		//! \return Size of node name, in characters.
		std::size_t getNameSize() const;

		//! Gets value of node.
		//! Interpretation of value depends on type of node.
		//! Note that value will not be zero-terminated if xml_parse_no_string_terminators option was selected during parse.
		//! <br><br>
		//! Use valueSize() function to determine length of the value.
		//! \return Value of node, or empty string if node has no value.
		tchar *getValue() const;

		//! Gets size of node value, not including terminator character.
		//! This function works correctly irrespective of whether value is or is not zero terminated.
		//! \return Size of node value, in characters.
		std::size_t getValueSize() const;

		///////////////////////////////////////////////////////////////////////////
		// Node modification

		//! Sets name of node to a non zero-terminated string.
		//! See \ref ownership_of_strings.
		//! <br><br>
		//! Note that node does not own its name or value, it only stores a pointer to it.
		//! It will not delete or otherwise free the pointer on destruction.
		//! It is responsibility of the user to properly manage lifetime of the string.
		//! The easiest way to achieve it is to use XmlMemoryPool of the document to allocate the string -
		//! on destruction of the document the string will be automatically freed.
		//! <br><br>
		//! Size of name must be specified separately, because name does not have to be zero terminated.
		//! Use name(const tchar *) function to have the length automatically calculated (string must be zero terminated).
		//! \param name Name of node to set. Does not have to be zero terminated.
		//! \param size Size of name, in characters. This does not include zero terminator, if one is present.
		void setName(const tchar *name, std::size_t size);

		//! Sets name of node to a zero-terminated string.
		//! See also \ref ownership_of_strings and XmlNode::name(const tchar *, std::size_t).
		//! \param name Name of node to set. Must be zero terminated.
		void setName(const tchar *name);

		//! Sets value of node to a non zero-terminated string.
		//! See \ref ownership_of_strings.
		//! <br><br>
		//! Note that node does not own its name or value, it only stores a pointer to it.
		//! It will not delete or otherwise free the pointer on destruction.
		//! It is responsibility of the user to properly manage lifetime of the string.
		//! The easiest way to achieve it is to use XmlMemoryPool of the document to allocate the string -
		//! on destruction of the document the string will be automatically freed.
		//! <br><br>
		//! Size of value must be specified separately, because it does not have to be zero terminated.
		//! Use value(const tchar *) function to have the length automatically calculated (string must be zero terminated).
		//! <br><br>
		//! If an element has a child node of type node_data, it will take precedence over element value when printing.
		//! If you want to manipulate data of elements using values, use parser flag xml_parse_no_data_nodes to prevent creation of data nodes by the parser.
		//! \param value value of node to set. Does not have to be zero terminated.
		//! \param size Size of value, in characters. This does not include zero terminator, if one is present.
		void setValue(const tchar *value, std::size_t size);

		//! Sets value of node to a zero-terminated string.
		//! See also \ref ownership_of_strings and XmlNode::value(const tchar *, std::size_t).
		//! \param value Vame of node to set. Must be zero terminated.
		void setValue(const tchar *value);

		///////////////////////////////////////////////////////////////////////////
		// Related nodes access

		//! Gets node parent.
		//! \return Pointer to parent node, or 0 if there is no parent.
		XmlNode<tchar> *getParent() const;

	protected:
		// Return empty string
		static tchar *nullstr();

		tchar *mName;					// Name of node, or 0 if no name
		tchar *mValue;					// Value of node, or 0 if no value
		std::size_t mNameSize;			// Length of node name, or undefined of no name
		std::size_t mValueSize;			// Length of node value, or undefined if no value
		XmlNode<tchar> *mParent;		// Pointer to parent node, or 0 if none
	};


	///////////////////////////////////////////////////////////////////////////
	// XML attribute

	//! Class representing attribute node of XML document.
	//! Each attribute has name and value strings, which are available through name() and value() functions (inherited from XmlBase).
	//! Note that after parse, both name and value of attribute will point to interior of source text used for parsing.
	//! Thus, this text must persist in memory for the lifetime of attribute.
	//! \param tchar Character type to use.
	template<typename tchar = char>
	class XmlAttribute: public XmlBase<tchar>
	{
		friend class XmlNode<tchar>;
	public:
		///////////////////////////////////////////////////////////////////////////
		// Construction & destruction

		//! Constructs an empty attribute with the specified type.
		//! Consider using XmlMemoryPool of appropriate XmlDocument if allocating attributes manually.
		XmlAttribute(void);

		///////////////////////////////////////////////////////////////////////////
		// Related nodes access

		//! Gets document of which attribute is a child.
		//! \return Pointer to document that contains this attribute, or 0 if there is no parent document.
		XmlDocument<tchar> *getDocument() const;

		//! Gets previous attribute, optionally matching attribute name.
		//! \param name Name of attribute to find, or 0 to return previous attribute regardless of its name; this string doesn't have to be zero-terminated if name_size is non-zero
		//! \param name_size Size of name, in characters, or 0 to have size calculated automatically from string
		//! \param case_sensitive Should name comparison be case-sensitive; non case-sensitive comparison works properly only for ASCII characters
		//! \return Pointer to found attribute, or 0 if not found.
		XmlAttribute<tchar> *getPreviousAttribute(const tchar *name = 0, std::size_t name_size = 0, bool case_sensitive = true) const;

		//! Gets next attribute, optionally matching attribute name.
		//! \param name Name of attribute to find, or 0 to return next attribute regardless of its name; this string doesn't have to be zero-terminated if name_size is non-zero
		//! \param name_size Size of name, in characters, or 0 to have size calculated automatically from string
		//! \param case_sensitive Should name comparison be case-sensitive; non case-sensitive comparison works properly only for ASCII characters
		//! \return Pointer to found attribute, or 0 if not found.
		XmlAttribute<tchar> *getNextAttribute(const tchar *name = 0, std::size_t name_size = 0, bool case_sensitive = true) const;

	private:
		XmlAttribute<tchar> *mPrevAttribute;	// Pointer to previous sibling of attribute, or 0 if none; only valid if parent is non-zero
		XmlAttribute<tchar> *mNextAttribute;	// Pointer to next sibling of attribute, or 0 if none; only valid if parent is non-zero
	};


	///////////////////////////////////////////////////////////////////////////
	// XML node

	//! Class representing a node of XML document.
	//! Each node may have associated name and value strings, which are available through name() and value() functions.
	//! Interpretation of name and value depends on type of the node.
	//! Type of node can be determined by using type() function.
	//! <br><br>
	//! Note that after parse, both name and value of node, if any, will point interior of source text used for parsing.
	//! Thus, this text must persist in the memory for the lifetime of node.
	//! \param tchar Character type to use.
	template<typename tchar = char>
	class XmlNode: public XmlBase<tchar>
	{
	public:
		///////////////////////////////////////////////////////////////////////////
		// Construction & destruction

		//! Constructs an empty node with the specified type.
		//! Consider using XmlMemoryPool of appropriate document to allocate nodes manually.
		//! \param type Type of node to construct.
		XmlNode(XmlNodeType type);

		///////////////////////////////////////////////////////////////////////////
		// Node data access

		//! Gets type of node.
		//! \return Type of node.
		XmlNodeType getType(void) const;

		///////////////////////////////////////////////////////////////////////////
		// Related nodes access

		//! Gets document of which node is a child.
		//! \return Pointer to document that contains this node, or 0 if there is no parent document.
		XmlDocument<tchar> *getDocument() const;

		//! Gets first child node, optionally matching node name.
		//! \param name Name of child to find, or 0 to return first child regardless of its name; this string doesn't have to be zero-terminated if name_size is non-zero
		//! \param name_size Size of name, in characters, or 0 to have size calculated automatically from string
		//! \param case_sensitive Should name comparison be case-sensitive; non case-sensitive comparison works properly only for ASCII characters
		//! \return Pointer to found child, or 0 if not found.
		XmlNode<tchar> *getFirstNode(const tchar *name = 0, std::size_t name_size = 0, bool case_sensitive = true) const;

		//! Gets last child node, optionally matching node name.
		//! Behavior is undefined if node has no children.
		//! Use firstNode() to test if node has children.
		//! \param name Name of child to find, or 0 to return last child regardless of its name; this string doesn't have to be zero-terminated if name_size is non-zero
		//! \param name_size Size of name, in characters, or 0 to have size calculated automatically from string
		//! \param case_sensitive Should name comparison be case-sensitive; non case-sensitive comparison works properly only for ASCII characters
		//! \return Pointer to found child, or 0 if not found.
		XmlNode<tchar> *getLastNode(const tchar *name = 0, std::size_t name_size = 0, bool case_sensitive = true) const;

		//! Gets previous sibling node, optionally matching node name.
		//! Behavior is undefined if node has no parent.
		//! Use parent() to test if node has a parent.
		//! \param name Name of sibling to find, or 0 to return previous sibling regardless of its name; this string doesn't have to be zero-terminated if name_size is non-zero
		//! \param name_size Size of name, in characters, or 0 to have size calculated automatically from string
		//! \param case_sensitive Should name comparison be case-sensitive; non case-sensitive comparison works properly only for ASCII characters
		//! \return Pointer to found sibling, or 0 if not found.
		XmlNode<tchar> *getPreviousSibling(const tchar *name = 0, std::size_t name_size = 0, bool case_sensitive = true) const;

		//! Gets next sibling node, optionally matching node name.
		//! Behavior is undefined if node has no parent.
		//! Use parent() to test if node has a parent.
		//! \param name Name of sibling to find, or 0 to return next sibling regardless of its name; this string doesn't have to be zero-terminated if name_size is non-zero
		//! \param name_size Size of name, in characters, or 0 to have size calculated automatically from string
		//! \param case_sensitive Should name comparison be case-sensitive; non case-sensitive comparison works properly only for ASCII characters
		//! \return Pointer to found sibling, or 0 if not found.
		XmlNode<tchar> *getNextSibling(const tchar *name = 0, std::size_t name_size = 0, bool case_sensitive = true) const;

		//! Gets first attribute of node, optionally matching attribute name.
		//! \param name Name of attribute to find, or 0 to return first attribute regardless of its name; this string doesn't have to be zero-terminated if name_size is non-zero
		//! \param name_size Size of name, in characters, or 0 to have size calculated automatically from string
		//! \param case_sensitive Should name comparison be case-sensitive; non case-sensitive comparison works properly only for ASCII characters
		//! \return Pointer to found attribute, or 0 if not found.
		XmlAttribute<tchar> *getFirstAttribute(const tchar *name = 0, std::size_t name_size = 0, bool case_sensitive = true) const;

		//! Gets last attribute of node, optionally matching attribute name.
		//! \param name Name of attribute to find, or 0 to return last attribute regardless of its name; this string doesn't have to be zero-terminated if name_size is non-zero
		//! \param name_size Size of name, in characters, or 0 to have size calculated automatically from string
		//! \param case_sensitive Should name comparison be case-sensitive; non case-sensitive comparison works properly only for ASCII characters
		//! \return Pointer to found attribute, or 0 if not found.
		XmlAttribute<tchar> *getLastAttribute(const tchar *name = 0, std::size_t name_size = 0, bool case_sensitive = true) const;

		///////////////////////////////////////////////////////////////////////////
		// Node modification

		//! Sets type of node.
		//! \param type Type of node to set.
		void setType(XmlNodeType type);

		///////////////////////////////////////////////////////////////////////////
		// Node manipulation

		//! Prepends a new child node.
		//! The perpended child becomes the first child, and all existing children are moved one position back.
		//! \param child Node to prepends.
		void prependNode(XmlNode<tchar> *child);

		//! Appends a new child node.
		//! The appended child becomes the last child.
		//! \param child Node to append.
		void appendNode(XmlNode<tchar> *child);

		//! Inserts a new child node at specified place inside the node.
		//! All children after and including the specified node are moved one position back.
		//! \param where Place where to insert the child, or 0 to insert at the back.
		//! \param child Node to insert.
		void insertNode(XmlNode<tchar> *where, XmlNode<tchar> *child);

		//! Removes first child node.
		//! If node has no children, behavior is undefined.
		//! Use firstNode() to test if node has children.
		void removeFirstNode(void);

		//! Removes last child of the node.
		//! If node has no children, behavior is undefined.
		//! Use firstNode() to test if node has children.
		void removeLastNode(void);

		//! Removes specified child from the node
		// \param where Pointer to child to be removed.
		void removeNode(XmlNode<tchar> *where);

		//! Removes all child nodes (but not attributes).
		void removeAllNodes(void);

		//! Prepends a new attribute to the node.
		//! \param attribute Attribute to prepends.
		void prependAttribute(XmlAttribute<tchar> *attribute);

		//! Appends a new attribute to the node.
		//! \param attribute Attribute to append.
		void appendAttribute(XmlAttribute<tchar> *attribute);

		//! Inserts a new attribute at specified place inside the node.
		//! All attributes after and including the specified attribute are moved one position back.
		//! \param where Place where to insert the attribute, or 0 to insert at the back.
		//! \param attribute Attribute to insert.
		void insertAttribute(XmlAttribute<tchar> *where, XmlAttribute<tchar> *attribute);

		//! Removes first attribute of the node.
		//! If node has no attributes, behavior is undefined.
		//! Use firstAttribute() to test if node has attributes.
		void removeFirstAttribute(void);

		//! Removes last attribute of the node.
		//! If node has no attributes, behavior is undefined.
		//! Use firstAttribute() to test if node has attributes.
		void removeLastAttribute(void);

		//! Removes specified attribute from node.
		//! \param where Pointer to attribute to be removed.
		void removeAttribute(XmlAttribute<tchar> *where);

		//! Removes all attributes of node.
		void removeAllAttributes(void);

	private:
		///////////////////////////////////////////////////////////////////////////
		// Restrictions

		// No copying
		XmlNode(const XmlNode &);
		void operator =(const XmlNode &);

		///////////////////////////////////////////////////////////////////////////
		// Data members

		// Note that some of the pointers below have UNDEFINED values if certain other pointers are 0.
		// This is required for maximum performance, as it allows the parser to omit initialization of
		// unneeded/redundant values.
		//
		// The rules are as follows:
		// 1. firstNode and firstAttribute contain valid pointers, or 0 if node has no children/attributes respectively
		// 2. lastNode and lastAttribute are valid only if node has at least one child/attribute respectively, otherwise they contain garbage
		// 3. prevSibling and nextSibling are valid only if node has a parent, otherwise they contain garbage

		XmlNodeType mType;                      // Type of node; always valid
		XmlNode<tchar> *mFirstNode;             // Pointer to first child node, or 0 if none; always valid
		XmlNode<tchar> *mLastNode;              // Pointer to last child node, or 0 if none; this value is only valid if mFirstNode is non-zero
		XmlAttribute<tchar> *mFirstAttribute;   // Pointer to first attribute of node, or 0 if none; always valid
		XmlAttribute<tchar> *mLastAttribute;    // Pointer to last attribute of node, or 0 if none; this value is only valid if mFirstAttribute is non-zero
		XmlNode<tchar> *mPrevSibling;           // Pointer to previous sibling of node, or 0 if none; this value is only valid if mParent is non-zero
		XmlNode<tchar> *mNextSibling;           // Pointer to next sibling of node, or 0 if none; this value is only valid if mParent is non-zero
	};


	///////////////////////////////////////////////////////////////////////////
	// XML document

	//! This class represents root of the DOM hierarchy.
	//! It is also an XmlNode and a XmlMemoryPool through public inheritance.
	//! Use parse() function to build a DOM tree from a zero-terminated XML text string.
	//! parse() function allocates memory for nodes and attributes by using functions of XmlDocument,
	//! which are inherited from XmlMemoryPool.
	//! To access root node of the document, use the document itself, as if it was an XmlNode.
	//! \param tchar Character type to use.
	template<typename tchar = char>
	class XmlDocument: public XmlNode<tchar>, public XmlMemoryPool<tchar>
	{
	public:
		//! Constructs empty XML document
		XmlDocument(void);

		//! Parses zero-terminated XML string according to given flags.
		//! Passed string will be modified by the parser, unless xml_parse_non_destructive flag is used.
		//! The string must persist for the lifetime of the document.
		//! In case of error, xml_parse_error exception will be thrown.
		//! <br><br>
		//! If you want to parse contents of a file, you must first load the file into the memory, and pass pointer to its beginning.
		//! Make sure that data is zero-terminated.
		//! <br><br>
		//! Document can be parsed into multiple times.
		//! Each new call to parse removes previous nodes and attributes (if any), but does not clear memory pool.
		//! \param text XML data to parse; pointer is non-const to denote fact that this data may be modified by the parser.
		template<int Flags>
		void parse(tchar *text);

		template<int Flags>
		void parse(const tchar *text);

		//! Clears the document by deleting all nodes and clearing the memory pool.
		//! All nodes owned by document pool are destroyed.
		void clear(void);

	private:
		///////////////////////////////////////////////////////////////////////
		// Internal character utility functions

		// Detect whitespace character
		struct WhitespacePred
		{
			static unsigned char test(tchar ch);
		};

		// Detect node name character
		struct NodeNamePred
		{
			static unsigned char test(tchar ch);
		};

		// Detect attribute name character
		struct AttributeNamePred
		{
			static unsigned char test(tchar ch);
		};

		// Detect text character (PCDATA)
		struct TextPred
		{
			static unsigned char test(tchar ch);
		};

		// Detect text character (PCDATA) that does not require processing
		struct TextPureNoWsPred
		{
			static unsigned char test(tchar ch);
		};

		// Detect text character (PCDATA) that does not require processing
		struct TextPureWithWsPred
		{
			static unsigned char test(tchar ch);
		};

		// Detect attribute value character
		template<tchar Quote>
		struct AttributeValuePred
		{
			static unsigned char test(tchar ch);
		};

		// Detect attribute value character
		template<tchar Quote>
		struct AttributeValuePurePred
		{
			static unsigned char test(tchar ch);
		};

		// Insert coded character, using UTF8 or 8-bit ASCII
		template<int Flags>
		static void insertCodedCharacter(tchar *&text, unsigned long code);

		// Skip characters until predicate evaluates to true
		template<typename StopPred, int Flags>
		static void skip(tchar *&text);

		// Skip characters until predicate evaluates to true while doing the following:
		// - replacing XML character entity references with proper characters (&apos; &amp; &quot; &lt; &gt; &#...;)
		// - condensing whitespace sequences to single space character
		template<typename StopPred, typename StopPredPure, int Flags>
		static tchar *skipAndExpandCharacterRefs(tchar *&text);

		///////////////////////////////////////////////////////////////////////
		// Internal parsing functions

		// Parse BOM, if any
		template<int Flags>
		void parseBom(tchar *&text);

		// Parse XML declaration (<?xml...)
		template<int Flags>
		XmlNode<tchar> *parseXmlDeclaration(tchar *&text);

		// Parse XML comment (<!--...)
		template<int Flags>
		XmlNode<tchar> *parseComment(tchar *&text);

		// Parse DOCTYPE
		template<int Flags>
		XmlNode<tchar> *parseDoctype(tchar *&text);

		// Parse PI
		template<int Flags>
		XmlNode<tchar> *parsePI(tchar *&text);

		// Parse and append data
		// Return character that ends data.
		// This is necessary because this character might have been overwritten by a terminating 0
		template<int Flags>
		tchar parseAndAppendData(XmlNode<tchar> *node, tchar *&text, tchar *contents_start);

		// Parse CDATA
		template<int Flags>
		XmlNode<tchar> *parseCdata(tchar *&text);

		// Parse element node
		template<int Flags>
		XmlNode<tchar> *parseElement(tchar *&text);

		// Determine node type, and parse it
		template<int Flags>
		XmlNode<tchar> *parseNode(tchar *&text);

		// Parse contents of the node - children, data etc.
		template<int Flags>
		void parseNodeContents(tchar *&text, XmlNode<tchar> *node);

		// Parse XML attributes of the node
		template<int Flags>
		void parseNodeAttributes(tchar *&text, XmlNode<tchar> *node);
	};


	///////////////////////////////////////////////////////////////////////////
	// Printing

	const int xml_print_no_indenting = 0x1;   //!< Printer flag instructing the printer to suppress indenting of XML. See print() function.

	//! Prints XML to given output iterator.
	//! \param out Output iterator to print to.
	//! \param node Node to be printed. Pass XmlDocument to print entire document.
	//! \param flags Flags controlling how XML is printed.
	//! \return Output iterator pointing to position immediately after last character of printed text.
	template<typename OutIterator, typename tchar>
	inline OutIterator XmlPrint(OutIterator out, const XmlNode<tchar> &node, int flags = 0);

}


#include "NightXML.inl"


#endif
